Bài thực hành 8: Mạng xã hội với đồ thị

Mục tiêu 🎯

  • Mô hình: Một mạng xã hội đơn giản.
    • Người dùng được biểu diễn dưới dạng đỉnh trong đồ thị.
    • Các mối quan hệ bạn bè là cạnh vô hướng.
  • Nhiệm vụ: Xử lý một chuỗi lệnh để xây dựng và truy vấn mạng lưới.

Cách biểu diễn 💾

Chúng ta sẽ sử dụng một Danh sách kề để lưu trữ đồ thị.

Đó là một mảng các danh sách. Danh sách tại chỉ số `i` lưu tất cả các bạn bè của người dùng `i`.

// Các mối quan hệ bạn bè: (0,1), (0,2), (1,2)
adj = [
0:[1, 2],
1:[0, 2],
2:[0, 1],
3:[],
]

Các thao tác ⚙️

Bạn sẽ triển khai bốn lệnh:

  • add u v

    Thêm một mối quan hệ bạn bè.

  • degree u

    Đếm số bạn bè của người dùng u.

  • isfriend u v

    Kiểm tra xem u và v có phải là bạn bè hay không.

  • count_greater x

    Đếm số người dùng có hơn x bạn bè.